\section{Background}
\label{sec:bg}

%\begin{figure}%\begin{center}%\includegraphics[height = 0.3\textwidth]{board_init}%\end{center}%\caption{The initial state of an Othello game, with black making the first move.  Black has four possible moves as indicated by the green highlighted squares.}\label{fig:board_init}%\end{figure}

\begin{figure}[htp]
\centering     \subfigure[The initial state of an Othello game, with black making the first move.  Black has four possible moves as indicated by the green highlighted squares.]{          \label{fig:board_init}          \includegraphics[width=.3\textwidth]{board_init}}     \hspace{.3in}     \subfigure[Black moves to square (6, 5) which flips the disc at (5, 5) from white to black.  Now white has 3 possible moves as indicated in green.]{          \label{fig:board_whitemove}          \includegraphics[width=.3\textwidth]{board_whitemove}}
	\caption{The initial board state for Othello and a board state after Black moves to (5,6).}
\end{figure}

Othello is a two-player game where the players alternate placing their corresponding color disc, either black or white, on an 8 $\times$ 8 game board.  Initially the game board is set up as in Figure~\ref{fig:board_init}, and the black player always goes first.  A player can place a disc on the board in any open location which neighbors a disc of the opposite color and there exists another one of the player's discs in the same direction (horizontal, vertical, or diagonal) as the neighbor.  Once a move is played, all opposite color discs between the player's two discs are flipped to the player's color.

As an example, in Figure~\ref{fig:board_init} we see that black has four possible moves as indicated by the green highlighted squares.  In each case the move borders a white disc and there exists a black disc in line with the white disc.  If the black player places a disc at (6, 5), the white discs between the newly placed black disc and the in line black disc are flipped to be black as in Figure~\ref{fig:board_whitemove}.  A more complex board configuration and moves are shown are Figure~\ref{fig:board_fullset}.

\begin{figure}[htp]
\centering     \subfigure[In this state it is White's move and they have 15 possible places to play as indicated by the green highlighted squares.]{          \label{fig:move1}          \includegraphics[width=.3\textwidth]{move1}}     \hspace{.1in}     \subfigure[It is now Black's move as White chose to place a disc at (7,2).  This move flipped the black discs in column 2 until the white disc at (4,2) was reached.  Similarly, the black discs along the diagonal were flipped until the white disc at (5,4) was reached.  Notice the black disc at (6,1) is not flipped.]{          \label{fig:move2}          \includegraphics[width=.3\textwidth]{move2}}
	\hspace{.1in}
	\subfigure[It is again White's move as Black chose to play in (8,1), the lower left corner.  This move flipped the white discs along the diagonal until the black disc at (4,5) was reached.]{
		  \label{fig:move3}
		  \includegraphics[width=.3\textwidth]{move3}}
	\caption{A set of board states in the middle of an Othello game beginning with White selecting a move on board (a).}
	\label{fig:board_fullset}
\end{figure}

Over the course of the game it is possible for a player to not have a legal move.  In this case, the turn is given to the opposite player.  If both players do not have legal moves, whether the board is full or not, the game is over.  Once over, the winner is determined by who has the most discs of their color in the board.

The mechanics of Othello are easy to master but the game still poses a significant challenge for both humans and computers alike.  Othello is a perfect knowledge game, but is divergent since the number of possible moves increase as the play continues before reaching the end game.  Also the state space, $3^{64}$ nodes, and the game-tree complexity, $~10^{58}$ states if we assume average game of 58 moves and 10 moves per state, are large enough to dissuade solving the game through enumeration methods \cite{allis:1994}.  Essentially the game is complex enough to require skill from humans and tremendous searching capabilities from computers.



 

%MiniMax with alpha beta if implemented

%ProbCut (if built)